﻿#define _CRT_SECURE_NO_WARNINGS
#pragma once
#include<iostream>
#include<vector>
using namespace std;

// 请完成哈希表的如下操作
// 哈希函数采用除留余数法﻿
template<class K>
struct HashFunc
{
	size_t operator()(const K& key)
	{
		return (size_t)key;
	}
};

// 哈希表中支持字符串的操作
//特化
template<>
struct HashFunc<string>
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

// 以下采用开放定址法，即线性探测解决冲突
namespace open_address
{
	enum State
	{
		EXIST,
		EMPTY,
		DELETE
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;
		State _state = EMPTY;
	};

	template<class K, class V, class Hash = HashFunc<K>>
	class HashTable
	{
	public:
		HashTable()
		{
			_tables.resize(10);
		}

		bool Insert(const pair<K, V>& kv) {
			if (Find(kv.first)) {
				return false;
			}
			
			//扩容
			if (_n * 10 / _tables.size() >= 0.7) {
				HashTable<K,V,Hash> New;
				New._tables.resize(_tables.size() * 3);

				for (int i = 0; i < _tables.size(); i++) {
					if (_tables[i]._state == EXIST) {
						New.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(New._tables);
			}
			
			Hash MyHashFunc;
			size_t HashValue = MyHashFunc(kv.first) % _tables.size();
			while (_tables[HashValue]._state == EXIST) {
				++HashValue;
				if (HashValue == _tables.size())
					HashValue = 0;
			}
			_tables[HashValue]._kv = kv;
			_tables[HashValue]._state = EXIST;
			++_n;
			return true;
		}
		HashData<K, V>* Find(const K& key) {
			Hash MyHashFunc;
			size_t HashValue = MyHashFunc(key) % _tables.size();
			while (_tables[HashValue]._state != EMPTY) {
				if (_tables[HashValue]._kv.first == key && _tables[HashValue]._state == EXIST)//把能直接判断返回的先写了
					return &_tables[HashValue];

				++HashValue;
				if (HashValue == _tables.size()) {
					HashValue = 0;//不会碰见全满的状态，因为负载因子为0.7
				}
			}//所以一定会碰见empty或delete停下来

			return nullptr;
		}
		bool Erase(const K& key) {
			if (!Find(key)) {
				return false;
			}

			HashData<K, V>* found = this->Find(key);
			found->_state = DELETE;
			--_n;
			return true;
		}
		void Print() {
			for (auto x : _tables) {
				if (x._state != EMPTY) {
					cout << x._kv.first << " " << x._kv.second << " " << x._state << endl;
				}
			}
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;  // 表中存储数据个数
	};
}

using namespace open_address;
int main() {
	HashTable<int, int> h;
	for (int i = 0; i < 20; i++) {
		h.Insert(make_pair(i, i+1));

	}
	cout << "插入后" << endl;
	h.Print();

	cout << "是否成功插入1:"<<h.Insert(make_pair(1, 1)) << endl;
	cout <<"1的赋值是："<< h.Find(1)->_kv.second << endl;
	cout << "是否成功删除1："<<h.Erase(1) << endl;
	cout << "删除后" << endl;
	h.Print();
	cout << "是否成功删除1：" << h.Erase(1) << endl;
	cout <<"是否成功找到1:"<< h.Find(1) << endl;


	return 0;
}

// 实现完成后，请对整形 和 字符串完成测试